package 热题100;

import java.util.Arrays;

public class 热题31下一个排列 {
    public static void main(String[] args) {
        int[] arr = {1,3,4,6,7,8,5};
        new 热题31下一个排列().nextPermutation(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int left = -1;
        //找最大数
        for(int i = len-1,j = len-2;i > 0 && j >= 0;i--,j--){
            if(nums[j] < nums[i]){//存在前一个数小于后一个数，那么就不是最大数
                left = i;
                break;
            }
        }
        if(left == -1){//最大数
            Arrays.sort(nums);
            return ;
        }else{
            left  = 0;
            int right = len-1;
            for(int i = len-1;i >=0 ;i --){
                boolean flag = false;
                for(int j = i-1;j >= 0 ;j--){
                    boolean point = false;
                    if(nums[i] > nums[j]){
                        left = j;//找到了比右边小的第一个数
                        right = i;
                        flag = true;
                        break;
                    }else {
                        if (j > 0 && nums[j-1] < nums[j]){
                            for(int k =nums.length-1;k > 0;k--){
                                if (nums[j-1] < nums[k]){
                                    left = j-1;
                                    right = k;
                                    flag = true;
                                    point = true;
                                    break;
                                }
                            }
                        }
                        if (point) break;
                    }
                }
                if (flag) break;
            }
            //此时index是第一个比右边小的数
            swap(nums,left,right);//交换index和右边的数：231 -》 231
            Arrays.sort(nums,left+1,nums.length);//在交换的后面的位置进行排序 231 -》231
        }
    }
    /**
     arr : 待排序数组
     left ：待排序区间的左边界
     right : 待排序区间的右边界
     */
    private void swap(int[] arr,int left,int right){
        int tem = arr[left];
        arr[left] = arr[right];
        arr[right] = tem;
    }
}
